package hot_100;

/**
 * @author: Darven
 * @createTime: 2025-09-26  01:17
 * @description: TODO
 */
public class P41 {
    public static void main(String[] args) {
        P41 p41 = new P41();
        p41.firstMissingPositive(new int[]{1,3,5,6,7});
    }
    //    public int firstMissingPositive(int[] nums) {
//        // 使用bitmap
//        int n=nums.length;
//        if(n<=1&&nums[0]!=1){
//            return 1;
//        }else if(n == 1){
//            return 2;
//        }
//        int maxNum=Integer.MIN_VALUE;
//        for(int i=0;i<n;i++){
//            if(nums[i]!=Integer.MAX_VALUE&&nums[i]!=Integer.MAX_VALUE-1&&nums[i]!=Integer.MAX_VALUE-2){
//                maxNum=Math.max(maxNum, nums[i]);
//            }
//        }
//        if(maxNum<0){
//            return 1;
//        }
//        boolean[] bitMap=new boolean[maxNum+2];
//
//        for(int i=0;i<n;i++){
//            if(nums[i]!=Integer.MAX_VALUE&&nums[i]!=Integer.MAX_VALUE-1&&nums[i]!=Integer.MAX_VALUE-2&&nums[i]>0){
//                bitMap[nums[i]]=true;
//            }
//        }
//
//        for(int i=1;i<=n;i++){
//            if(!bitMap[i]){
//                return i;
//            }
//        }
//        return maxNum+1;
//    }
    public void firstMissingPositive(int[] nums) {
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            // 满足条件：是正整数、小于等于n、且当前位置不是它应该在的位置
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // 交换 nums[i] 到它应该在的位置（索引 = 数值 - 1）
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for(int i=0;i<n;i++){
            System.out.println(nums[i]);
        }
    }

}
